We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-basedalgorithm that is asymptotically near-optimal. Namely, the solution extractedfrom LBT-RRT converges to a solution that is within an approximation factor of1+epsilon of the optimal solution. Our algorithm allows for a continuousinterpolation between the fast RRT algorithm and the asymptotically optimalRRT* and RRG algorithms. When the approximation factor is 1 (i.e., noapproximation is allowed), LBT-RRT behaves like RRG. When the approximationfactor is unbounded, LBT-RRT behaves like RRT. In between, LBT-RRT is shown toproduce paths that have higher quality than RRT would produce and run fasterthan RRT* would run. This is done by maintaining a tree which is a sub-graph ofthe RRG roadmap and a second, auxiliary graph, which we call the lower-boundgraph. The combination of the two roadmaps, which is faster to maintain thanthe roadmap maintained by RRT*, efficiently guarantees asymptoticnear-optimality. We suggest to use LBT-RRT for high-quality, anytime motionplanning. We demonstrate the performance of the algorithm for scenarios rangingfrom 3 to 12 degrees of freedom and show that even for small approximationfactors, the algorithm produces high-quality solutions (comparable to RRG andRRT*) with little running-time overhead when compared to RRT.
展开▼
